/*--- quick4.c ---------------------------- Listing 5-10 --------
 * Quicksort with median-of-three partitioning
 * based on a randomly selected middle element,
 * insertion sort on small subfiles, removal of
 * end recursion, and use of pointer
 * incrementing rather than an index.
 *
 * Uses InsertionSort() from insert.c (Listing 5-5)
 *
 * #define DRIVER to compile a test driver
 * Driver must be linked to sortsub.c (Listing 5-1)
 *-------------------------------------------------------------*/

#include <stddef.h>     /* for typedef of ptrdiff_t */
#include <stdlib.h>     /* for rand() */
#include "sorthdr.h"

#define DRIVER 1

static CompFunc StoredCompare;

static void xQuickSort4(Element **pL, Element **pR)
{
    ptrdiff_t diff; /* ptrdiff_t is a signed type that can hold
                       the difference between two pointers */

    while ((diff = (pR - pL)) >= 9) { /* 10 elements a must */
        int mid;
        Element *temp, **pmid, **pi, **pj, *ppivot;

        /* select a random mid element */
        mid = abs (rand()) % diff;
        if (mid < 1 || mid > diff - 2)
            mid = 1;
        pmid = pL + mid;

        /*
         * Sort Lth, Rth, and middle element. Then swap the
         * middle element with the R-1'th element. This will
         * obviate the need for bound checking.
         */
        if (StoredCompare(*pL, *pmid) > 0) {
            temp = *pL;
            *pL = *pmid;
            *pmid = temp;
        }
        if (StoredCompare(*pL, *pR) > 0) {
            temp = *pL;
            *pL = *pR;
            *pR = temp;
        }
        if (StoredCompare(*pmid, *pR) > 0) {
            temp = *pmid;
            *pmid = *pR;
            *pR = temp;
        }

        temp = *pmid;
        *pmid = *(pR - 1);
        *(pR - 1) = temp;

        /*
         * Now, we know that Array[L] <= Array[R-1] <= Array[R].
         * We use Array[R-1] as the pivot, so this relationship
         * gives us known sentinels. Also, we need to partition
         * only between L+1 and R-2.
         */
        pi = pL;       /* Scan up from here */
        pj = pR - 1;   /* Scan down from here */
        ppivot = *pj;
        for ( ; ; ) {
            /* Looking from left, find element >= Array[R-1] */
            while (StoredCompare(*++pi, ppivot) < 0)
                ;

            /* Looking from right, find element <= Array[R-1] */
            while (StoredCompare(*--pj, ppivot) > 0)
                ;

            if (pi >= pj )
                break;

            /* swap ith and jth elements */
            temp = *pi;
            *pi = *pj;
            *pj = temp;
        }

        /* swap ith and the pivot */
        *(pR - 1) = *pi;
        *pi = ppivot;

        if (pi - pL > pR - pi) { /* left half is larger */
            xQuickSort4(pi + 1, pR); /* recurse on smaller half */
            pR = pi - 1;
        } else {   /* right half is larger */      
            xQuickSort4(pL, pi-1);
            pL = pi + 1;
        }
    }
}

void QuickSort4(Element **Array, int Items, CompFunc Compare)
{
    void InsertionSort(Element **, int, CompFunc);

    /* Save some things */
    StoredCompare = Compare;

    /* Quicksort to get nearly sorted file */
    xQuickSort4(Array, Array + Items - 1);

    /* Do an insertion sort on the now nearly sorted file */
    InsertionSort(Array, Items, Compare);
}

#ifdef DRIVER
#include <stdio.h>
#include <string.h>
#include "sortsub.h"

/*
 * A comparison function
 */
int Cfunc(Element *L, Element *R)
{
    return (strncmp(L->text, R->text, 5));
}

void main(int argc, char *argv[])
{
    Element **Array;
    int Items = 2000;

    if (argc != 2 && argc != 3) {
        fprintf(stderr, "Usage: quick4 infile [maxitems]\n");
        return;
    }

    if (argc == 3)
        Items = atoi(argv[2]);

    if ((Items = LoadArray(argv[1], Items, &Array)) == -1)
        return; /* Couldn't load file */

    QuickSort4(Array, Items, (CompFunc)Cfunc);
    ShowArray(Array, Items, (CompFunc)Cfunc);
}
#endif
